package com.data_structure_algorithm.algorithm;

import java.util.Arrays;

/**
 * @Author PABLO
 * @Date 2022/4/8 21:14
 * @Desc 非KMP方式存在大量回溯
 */
public class KMP {

    public static void main(String[] args) {
        String a = "asdfghjkl";
        String b = "dfghj";

        int result = violenceMatch(a, b);
        System.out.println(result);


    }

    /**
     * @Description: str1中查询str2子串是否存在，存在返回首次出现下标，否则-1
     * @Author: PABLO
     * @Date: 2022/4/8 21:15
     * @Params: [str1, str2]
     * @Return: int  缺点大量回溯
     **/
    private static int violenceMatch(String str1, String str2) {
        char[] father = str1.toCharArray();
        char[] son = str2.toCharArray();

        //遍历father 和 son，用son的首元素匹配father
        int sonIndex = 0;
        int fatherIndex = 0;

        for (; sonIndex < son.length && fatherIndex < father.length; ) {
            if (son[sonIndex] != father[fatherIndex]) {
                // father就复位到最早和son匹配的下一个位置
                //如两字符串在father==5的位置匹配成功，father和son均++，继续往后比较，但是下一次不相同了
                //，son需复位到0，等待下次比较，father将回到==6的位置
                fatherIndex = fatherIndex - (sonIndex - 1);
                //son复位，等待下次右相同的father值出现，只要不完全相符，son就需要复位，
                sonIndex = 0;
            } else {
                fatherIndex++;
                sonIndex++;
                if (sonIndex == son.length) {
                    return fatherIndex - sonIndex;
                }
            }
        }
        return -1;
    }
}

class KMP2 {


    public static void main(String[] args) {

        String a = "BBC ABCDAB ABCDABCDABDE";
        String b = "ABCDABD";
        int[] index = getTable(b);
        System.out.println(Arrays.toString(index));
        int i = violenceMatch(a, b);
        System.out.println(i);


    }

    /**
     * @Description:father串不回溯，son回溯到某个指定位置
     * @Author: PABLO
     * @Date: 2022/6/25 12:10
     * @Params:
     * @Return:
     **/
    private static int violenceMatch(String father, String son) {
        if (father == null || son == null) return -1;
        //子串和主串的匹配过程
        int fatherLen = father.length();
        int sonLen = son.length();
        if (fatherLen == 0 || sonLen == 0) return -1;

        //辅助变量
        int i = 0;
        int j = 0;
        while (i < fatherLen && j < sonLen) {
            if (father.charAt(i) != son.charAt(j)) {
                //不匹配  i不动,j回退到指定位置
                j = getTable(son)[j];
            }
            if (father.charAt(i) == son.charAt(j)) {
                j++;
            }
            i++;
        }

        //j的长度==子串长度说明找到了
        if (j == sonLen) {
            return i - j;
        }
        return -1;

    }


    //获得next数组，以确定son串的回溯位置
    public static int[] getTable(String str) {
        if (str.length() == 0 || str == null) return null;
        int[] table = new int[str.length()];
        table[0] = 0;
        //如果字符串长度是1，那么匹配值为0
        if (str.length() == 1) {
            return table;//table下标对应str对应字符的匹配数量
        }
        //i从str下标1字符开始
        //j代表i的前一个字符
        for (int i = 1, j = 0; i < str.length(); ) {
            //如i和i的前一个字符j不相等  需获取新的j，即现在j的前面一个值
            //一直循环到i和j<<相等为止,为了满足str.charAt(i) == str.charAt(j) i++ == j++的公式
            //一直找到相等为止，从相等位置开始绑定table[i]和j的位置
            if (str.charAt(i) != str.charAt(j)) {
                j = table[j];
            }
            //当前i字符和前一个字符比较
            //如相等，说明i + 1 == j + 1
            if (str.charAt(i) == str.charAt(j)) {
                j++;
            }
            //每次正常循环都++，判断是否越界,for循环的执行规则，放在上面括号里，会++晚一步，
            // j = table[j];就得变成 j = table[j - 1];
            i++;
            //table[i]对应子串str对应下标回退的位置
            //如table[5] == 3,说明子串str下标5的位置对应字符回退到str下标3的位置
            if (i < str.length()) {
                table[i] = j;
            }


        }
        return table;
    }
}



